1. Field of the Invention
This invention relates to a new method and apparatus for generating a bit reversed sequence. More particularly, the invention teaches a reverse addition means which adds binary words in most significant to least significant bit order with the overflow or carry bit propagated to the left. The reverse addition means can be used in an address generator to generate a bit reversed address and/or an address sequence that is mapped into a "closed" space.
2. Description of the Prior Art
Most FFT (Fast Fourier Transform) algorithms require bit reversal addressing of either the input or output data buffer in order for the output sequence of the algorithm to be in natural order. For example, an eight-point decimation in time FFT algorithm requires the input sequence to be stored in the shuffled order x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7) for the output data order to be X(0), X(1), X(2), X(3), X(4), X(5), X(6), X(7). A simple definition of bit reversed order is thus: If one forms the K-bit binary representation of the natural order indices of a sequence of numbers, where the number of numbers in the sequence is a power of 2, and reverses the bits in the binary representation of the indices the resulting numbers are the indices of the bit reversed sequence of numbers. The process is shown in Table 1 for a sequence of N=8 numbers, i.e., K=3.
TABLE 1 ______________________________________ Binary Bit Reversed Bit Reversed Index Representation Binary Index ______________________________________ 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 ______________________________________
In Table 1 the natural order indices are as shown at the left, whereas the bit reversed indices are as shown at the right of the table. Table 2 shows the same process for N=16. Note that the result depends on the order (K) of the sequence. Thus, in order to shuffle a sequence from its natural order to a bit reversed order, either bit reversing hardware or an algorithm is required in addressing the buffer containing the sequence.
TABLE 2 ______________________________________ Binary Bit Reversed Bit Reversed Index Representation Binary Index ______________________________________ 0 0000 0000 0 1 0001 1000 8 2 0010 0100 4 3 0011 1100 12 4 0100 0010 2 5 0101 1010 10 6 0110 0110 6 7 0111 1110 14 8 1000 0001 1 9 1001 1001 9 10 1010 0101 5 11 1011 1101 13 12 1100 0011 3 13 1101 1011 11 14 1110 0111 7 15 1111 1111 15 ______________________________________
One prior art method is to use hardware logic to directly reverse the address bits going to a buffer. This method is implemented either by wiring the bits in reversed order to the buffer or by using a multiplexer to select the designation of each address bit. The first implementation is limited to applications requiring only one fixed size address space (e.g., only one Fast Fourier Transform size). The second prior art implementation requires the multiplexer to be designated for a predefined number of address space sizes.
Another prior art method is to use a bit reversed counter program. The following shows a typical flow chart used for such a prior art method: ##STR1## Beginning with the first bit reversed number, 000 in Table 1 or 2, the program generates the remaining bit reversed indices in order. This method is usually implemented using a computer or microprocessor, and is too slow for high speed FFT hardware applications.
U.S. Pat. No. 4,181,976 discloses a prior art bit reverse apparatus that is adapted for use as an address generator for an FFT processor.